import java.util.*;

public class 二叉树的层序遍历 {


  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
          this.right = right;
     }
  }
    public List<List<Integer>> ans;
    List<Integer> path = new ArrayList<>();

    public TreeNode[] queue = new TreeNode[2001];
    public int l,r;
    public List<List<Integer>> levelOrder(TreeNode root) {
        ans = new ArrayList<>();
        path = new ArrayList<>();
        l = r = 0;
        // 判空处理
        if (root == null) {
            return ans;
        }
        // 添加头节点
        queue[r++] = root;
        // 手写队列
        while (l < r) {
            int size = r - l;
            while (size-- > 0) {
                TreeNode t = queue[l++];
                path.add(t.val);
                // 不为空添加新的节点
                if (t.left != null) {
                    queue[r++] = t.left;
                }
                if (t.right != null) {
                    queue[r++] = t.right;
                }
            }
            ans.add(new ArrayList<>(path));
            path.clear();
        }
        return ans;
    }
}
